#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int MAXN = 2e5 + 10;
const int MAXM = 5e5 + 10;

struct Edge {
    int to, next, w;
} e[MAXM << 1];

int head[MAXN], idx = 1;
int col[MAXN];


int t, n, m;
int white, black;
bool flag;

void add_edge(int u, int v, int w) {
    e[idx].to = v;
    e[idx].next = head[u];
    e[idx].w = w;
    head[u] = idx++;
}

void clear_graph() {
    memset(head, -1, sizeof(int) * (n + 5));
    memset(e, 0, sizeof(int) * (m + 5) * 2);
    memset(col, 0, sizeof(int) * (n + 5));
    // memset(head, -1, sizeof(head));
    // memset(e, 0, sizeof(e));
    // memset(col, 0, sizeof(col));
    idx = 1;
}



// i->j, 给j染色
void paint(int i, int j, int w) {
    col[j] = w ? 3 - col[i] : col[i];
    // printf("为%d点染色为%d, 根据边<%d,%d,%d>\n", j, col[j], i, j, w);
}

bool check(int i, int j, int w) {
    return w ? (col[i] != col[j]) : (col[i] == col[j]);
}

void dfs(int u, int fa = -1) {
    // cout << u << endl;
    if (col[u] == 1) white++;
    else black++;

    for (int i = head[u]; ~i; i = e[i].next) {
        int j = e[i].to;

        // printf("正在遍历边： <%d->%d>, 权值为：%d\n", u, j, e[i].w);
        if (!col[j]) {
            paint(u, j, e[i].w);
            dfs(j, u);
        }
        else if (!check(u, j, e[i].w)) {
            flag = false;
        }

    }
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    cin >> t;
    while (t--) {
        cin >> n >> m;
        clear_graph();

        int u, v;
        string c;
        for (int i = 1; i <= m; i++) {
            cin >> u >> v >> c;
            // 不同阵营
            if (c == "imposter") {
                add_edge(u, v, 1);
                add_edge(v, u, 1);
            }
            else {
                add_edge(u, v, 0);
                add_edge(v, u, 0);
            }
        }

        int res = 0;
        flag = true;
        for (int i = 1; i <= n; i++) {
            if (!col[i] && flag) {
                white = black = 0;
                col[i] = 1;
                dfs(i);
                res += max(white, black);
            }

            // if (!flag) {
            //     res = -1;
            //     break;
            // }
        }
        if (!flag) res = -1;
        cout << res << endl;
    }
    return 0;
}